package sort;

/*
    快排：
        每次选择一个基准元素（我们就选第一个）
            把它放在应该放的位置，比它小的在它的左边，比它大的在右边，以此类推递归
        首先备份第一个元素到temp --> 这个时候左边这个元素就可以被替代了 (while leftIndex < rightIndex)
            从右往左扫进行 rightIndex-- ，符合条件则 array[leftIndex++] = array[rightIndex]
            从左往右扫进行 leftIndex++ ，符合条件 array[rightIndex--] = array[leftIndex]
        最后leftIndex应该是==rightIndex的，直接赋值 array[leftIndex] = temp 即可
        最后递归循环：
            quickSort(array, left, leftIndex-1)
            quickSort(array, leftIndex+1, right)

    总结：
        快排和归并最好都进来就备份一下left、right
        归并：
            需要额外的空间
            时间复杂度都为 O(nlogn)
            空间复杂度 O(n)
        快排：
            原地修改，不申请多余空间
            时间复杂度平均O(nlogn)，最坏O(n^2)
            空间复杂度，调用栈O(logn)，其余O(1)
 */
public class QuickSort {

    public static void main(String[] args) {
//        // 生成数组并打印
//        // int[] array = Util.getRandomArray();
//        int[] array = new int[]{3, 2, 4, 7, 5, 5};
//        Util.printArrayFormat(array);
//
//        // 使用函数
//        quickSort(array, 0, array.length - 1);
//
//        // 打印排序后的函数
//        Util.printArrayFormat(array);
//
//        // 判断是否排对了
//        System.out.println(Util.isSorted(array) ? "排对了" : "排错了");
        boolean isSorted = false;

        for (int i = 0; i < 10000; i++) {
            // 生成数组并打印
            int[] array = Util.getRandomArray();

            // 使用函数
            quickSort(array, 0, array.length - 1);

            // 判断是否排对了
            isSorted = Util.isSorted(array);
            if (!isSorted) break;
        }

        System.out.println(isSorted ? "对了" : "错了");
    }

    public static void quickSort(int[] array, int left, int right) {
        if (right - left <= 0) {
            return;
        }

        // 直接选择开始的第一个作为基准
        int leftIndex = left, rightIndex = right;
        int temp = array[leftIndex];

        while (leftIndex < rightIndex) {
            while (array[rightIndex] >= temp && rightIndex > leftIndex) {
                rightIndex--;
            }
            if (rightIndex > leftIndex && array[rightIndex] < temp) {
                array[leftIndex++] = array[rightIndex];
            }

            while (array[leftIndex] <= temp && leftIndex < rightIndex) {
                leftIndex++;
            }
            if (leftIndex < rightIndex && array[leftIndex] > temp) {
                array[rightIndex--] = array[leftIndex];
            }
        }
        // 此时leftIndex == rightIndex
        array[leftIndex] = temp;

        quickSort(array, left, leftIndex - 1);
        quickSort(array, leftIndex + 1, right);
    }
}
